package backtrackAlgorithm;


import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class LeetCode_131 {
    public List<List<String>> partition(String s) {
        ArrayList<List<String>> lists = new ArrayList<>();
        solution_1(s,lists,new ArrayList<String>(),0);
        return lists;

    }

    @Test
    public void test(){
//        partition("aab");
        System.out.println(check("a"));
    }

    private void solution_1(String str, ArrayList<List<String>> lists, ArrayList<String> list, int index) {
        if (index>=str.length()){
            lists.add(new ArrayList<>(list));
        }
        for (int i = index; i < str.length(); i++) {
            String substring = str.substring(index, i+1);
            if (check(substring)){      //回文
                list.add(substring);
                solution_1(str,lists,list,i+1);
                list.remove(list.size()-1);
            }
        }

    }

    private boolean check(String substring) {
        if (substring.equals("")){
            return false;
        }
        StringBuffer str = new StringBuffer(substring);
        StringBuffer reverse = str.reverse();
        return substring.equals(reverse.toString());
    }


}
